package ljl.alg.jianzhioffer.round3.medium;

import java.util.*;

public class _38_permutation {

    class stupid {
        public String[] permutation(String s) {
            Set<String> res = new HashSet<>();
            back(res, 0, s.toCharArray());
            return res.toArray(new String[0]);
        }

        void back(Set<String> set, int k, char[] arr) {
            if (k == arr.length)
                set.add(new String(arr));
            else {
                for (int i = k; i < arr.length; i++) {
                    swap(arr, i, k);
                    back(set, k + 1, arr);
                    swap(arr, i, k);
                }
            }
        }

        void swap(char[] arr, int i, int j) {
            if (i != j) {
                char t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
    }

    class lufei {
        char[] arr;
        List<String> res = new ArrayList<>();
        public String[] permutation(String s) {
            arr = s.toCharArray();
            dfs(0);
            return res.toArray(new String[0]);
        }
        void dfs(int x) {
            if (x == arr.length - 1) {
                res.add(new String(arr));
                return;
            }
            BitSet set = new BitSet();
            for (int i = x; i < arr.length; i++) {
                if (set.get(arr[i])) continue;
                set.set(arr[i]);
                swap(i, x);
                dfs(x + 1);
                swap(i, x);
            }
        }
        void swap(int i, int j) {
            if (i != j) {
                char t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
    }
}
